package org.lql.algo.codecrush.week010;

import org.lql.algo.common.TreeNode;

/**
 * @author: liangqinglong
 * @date: 2025-08-30 15:30
 * @description: 105. 从前序与中序遍历序列构造二叉树 <a href="https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/">...</a>
 **/
public class BuildTree {

	int[] preorder;
	int[] inorder;

	public TreeNode buildTree(int[] preorder, int[] inorder) {
		this.preorder = preorder;
		this.inorder = inorder;
		return build(0, preorder.length - 1, 0, inorder.length - 1);
	}

	public TreeNode build(int preStart, int preEnd, int inStart, int inEnd) {
		// 边界判断：如果左边界超过右边界，说明没有元素可操作
		if (preStart > preEnd) {
			return null;
		}
		// 前序遍历的第一个点是根节点 -> preOrder的左边界就是根节点的值
		TreeNode root = new TreeNode(preorder[preStart]);
		// 寻找中序遍历中的根节点所在位置
		int mid = inStart;
		while (inorder[mid] != root.val) {
			mid++;
		}
		// inStart ~ mid-1 左子数的中序
		// mid+1 ～ inEnd 右子数的中序
		// 构造左子数：
		//  前序：preStart + 1 ~ preStart + (mid - 1 - inStart + 1)
		//  中序：inStart ~ mid -1
		// 构造右子数
		//  前序： preStart + 1 + （mid - inStart）~ preEnd
		root.left = build(preStart + 1, preStart + (mid - inStart), inStart, mid - 1);
		root.right = build(preStart + (mid - inStart) + 1, preEnd, mid + 1, inEnd);
		return root;
	}
}
